'''
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
层次遍历的话 每次对队列做一个类似快照的操作标记这次遍历是一个层次 for _ in range(0, len(queue)):
之后入队的就是新的一层了
'''
from util.TreeHelper import *
from typing import List


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        queue = []
        if root:
            queue.append(root)
        while queue:
            tmp = []
            for _ in range(0, len(queue)):
                root = queue.pop(0)
                if root:
                    tmp.append(root.val)
                    queue.append(root.left)
                    queue.append(root.right)
            if tmp:
                res.append(tmp)
        return res


if __name__ == "__main__":

    print(Solution().levelOrder(genTreeFromStr("[3,9,20,null,null,15,7]")))
